找数字-网易校招

发表于 | 分类于 | 评论数： | 阅读次数：
本文字数： 800 | 阅读时长 ≈ 1 分钟

题目描述

给定一个数组，除了第一个出现1次之外，其余全都出现3次。找出出现一次的值。如：{1, 2, 1, 2, 1, 2, 7}, 找出7.

分析与解法

我们以数组[1, 2, 3, 1, 2, 1, 2]举例，将数组元素用二进制表示：

1
2
3
4
5
6
7
0 1
1 0
1 1
0 1
1 0
0 1
1 0

如果理解了上题，此题的思路似乎也就呼之欲出了。我们也可以按位运算，计算1 bit的数量，如果每个数字都出现三次，那么每位上的1 bit数量肯定是3的倍数，相反如果不是3的倍数，那么就是那个特殊的数在捣蛋。

我们似乎需要这么一种“加法”运算，使得每位上的 1 bit 数量能够得到累计，并且累计到了3就自动清零。但是理想是美好的，现实是残酷的，并没有这样一种神奇的运算（三进制？）。

但是我们可以用一个数“辅助”，因为每一位的1 bit数量统计都是类似的，所以假设正在统计某一位的1 bit数量。我们用a来表示 1 bit 的数量，当 1 bit的数量为0时，a=0；当数量为1时，a=1；当数量为2时，a=2？非也，位运算只能表示0和1，所以这时我们引进第二个变量b，我们用b=1来代表已经有了2个 1 bit，所以当有两个 1 bit 时，a=0,b=1。数量统计结果逢3化0，所以只有0、1、2三种结果：

1
2
3
4
bits数量 a b
   0     0 0
   1     1 0
   2     0 1

思路也就显而易见了，每次运算我们维护a和b的值，运算到最后即可得到结果：

1
2
3
4
5
6
7
8
$c = array(1, 2, 1, 2, 1, 2, 7);
$a = 0;
$b = 0;
for ($i=0; $i < count($c); $i++) { 
    $b = $a & ($b ^ $c[$i]);
    $a = $b | ($a ^ $c[$i]);
}
echo $a; 7